package leetcode101.search_problem.bfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code4
 * @Description 130. 被围绕的区域
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-07 8:56
 */
public class Code4 {

    public static int[] directions = new int[]{-1, 0, 1, 0, -1};

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'X','X','X','X'},
                {'X','X','O','X'},
                {'X','O','X','X'},
                {'X','O','X','X'}
        };
        solve(board);
    }

    public static void solve(char[][] board) {
        List<int[]> coordinates = new ArrayList<>(); // 创建一个坐标集合，保存以下不被标记的O们，返回值需要的
        Queue<int[]> queue = new LinkedList<>(); // 创建bfs需要的队列

        int m = board.length;
        int n = board[0].length;

        /*
        找到边界上是'O'的地方
         */
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                queue.offer(new int[]{i, 0});
            }
            if (board[i][n - 1] == 'O') {
                queue.offer(new int[]{i, n - 1});
            }
        }

        for (int i = 1; i < n - 1; i++) {
            if (board[0][i] == 'O') {
                queue.offer(new int[]{0, i});
            }
            if (board[m - 1][i] == 'O') {
                queue.offer(new int[]{m - 1, i});
            }
        }

        while (!queue.isEmpty()) {
            int[] head = queue.poll();
            int x = head[0];
            int y = head[1];
            if (x > -1 && x < m && y > -1 && y < n && board[x][y] == 'O') {
                coordinates.add(new int[]{x, y});
                board[x][y] = 'X';
                for (int i = 0; i < directions.length - 1; i++) {
                    queue.add(new int[]{x + directions[i], y + directions[i + 1]});
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
        for (int[] temp : coordinates) {
            board[temp[0]][temp[1]] = 'O';
        }

    }
}
/*
被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 
任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。
如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
具体思路：
找到边界上的O，然后对边界上的O进行广度优先搜索，找到和这个O相邻的其他O，把这些O的坐标保存在List集合中
在遍历过程中，将已经遍历的O改成X防止它们回溯
 */